01 分式规划

我们需要求解这样的问题：给定长度为 $n$ 的序列 $V$ 和 $C$ ($\forall i\in[1,n],C_i>0$)，求

或者说，给定 $n$ 维列向量 $\boldsymbol{v}$ 和 $\boldsymbol{c}$ ($\forall i\in[1,n],\boldsymbol c_i>0$)，求

其中 $\boldsymbol x$ 是一个行向量。这就是最基本的 01 分式规划问题。

问题转化

设分式等于 $r$。即

设 $f(s)={\sum_{i=1}^n V_ix_i}-s\cdot{\sum_{i=1}^n C_ix_i}$。对于任意一个 $x$，都可以求出一条直线 $y=f(s)$。当 $f(s)=0$ 时，$s=r$。

也就是说，平面上有若干条斜率为负的直线，要求出直线与 $x$ 轴交点的最大值（最右边的点）。

二分法

假设随便取一个 $s$。对于所有的 $f$，若存在 $f(s)\geq 0$，那么这条 $y=f(x)$ 与 $x$ 轴的交点一定在 $s$ 的右边。否则，没有交点在 $s$ 的右边，答案一定在 $s$ 左边。

这是一个很经典的二分答案的形式，所以就二分答案做了。关键是，如何判断存在 $f(s)\geq 0$？

其实就是判断 $\max_f\{f(s)\}\geq 0$。就是，已知 $s$，要求 ${\sum_{i=1}^n V_ix_i}-s\cdot{\sum_{i=1}^n C_ix_i}$ 的最大值。这个就很简单了。将式子转化为 ${\sum_{i=1}^n (V_i-sC_i)x_i}$。显然贪心可以做，若 $V_i-sC_i$ 是正数我们就取，否则不取。

设答案精度为 $\epsilon$ （因为分式通常是小数答案），那么复杂度是 $O(n\log \epsilon^{-1})$。

Dinkelbach

还是刚才的思路，仅略作改变。若 $\max_f\{ f(s)\}\geq 0$，那么我们贪心地，顺着这条 $y=f(x)$ 找到它与 $x$ 轴的交点，把这个交点作为新的 $s$，继续求解。这就是 Dinkelbach 算法。

Dinkelbach 解决 01 分数规划的复杂度是 $O(n\log v)$，并且有跑不满、常数小的优势。证明留坑待填。先放一个网上的证明：对于0-1分数规划的Dinkelbach算法的分析。

带限制的规划

有时候不一定是可以随便选。下面将提及几种带限制问题。

带限制问题，总体思路也不变，只是如何判断 $\max_f\{ f(s)\}\geq 0$ 罢了。

选不超过 $k$ 个

这个简单。就在选正数的基础上，只选前 $k$ 大的就可以了。

选择不能相邻

做一个 dp 即可。设 $dp_{i,0/1}$ 表示第 $i$ 个选或未选，贡献的最大值。那么 $dp_{i,0}=\max(dp_{i-1,0},dp_{i-1,1}),dp_{i,1}=dp_{i-1,0}+v_{i}$。

选择有树形依赖

比如 Desert King 那道题。求一个最大生成树即可。

也有可能是树形 dp。

选择不超过 $k$ 个，且不能相邻

做一个反悔贪心板子。类似题目：CTSC2007 数据备份。

选择的 $C$ 的和有上下界

也就是，$L\leq\sum C_ix_i\leq R$ 这种。可以用背包 dp。板题：[USACO18OPEN] Talent Show G

只能选择连续一段，并且选择的 $C$ 的和有上下界

连续一段可以前缀和。也就是判断是否存在 $\frac {V_i-V_j}{C_i-C_j}\geq s$。移项可得 $V_i-V_j\geq s(C_i-C_j)$，再变成是否存在 $V_i-sC_i\geq V_j-sC_j$。

注意到每个 $i$ 对应的 $j$ 也是连续的一段，并且单调，可以双指针维护段的左右端点。然后单调队列滑动窗口求解。

总之 01 分式规划不难。但是将一个问题转化成 01 分式规划可能需要一定的思维。

感觉越写越水了。就讲到这里吧。